#include <stdio.h>
#include <stdlib.h>

#define datatype int
#define P 7 //要是一个素数
#define NULL_DATA -1
#define BUCKET_NODE_SIZE 3

struct bucket_node
{
        int data[BUCKET_NODE_SIZE];
        struct bucket_node *next;
};

struct bucket_node hash_table[P];

void Inithash_table();

void Insert_new_element(datatype *key);

void Showhash_table();

int main(void)
{
        datatype ar[] = {1, 8, 15, 22, 29, 36, 43};
        int n = sizeof(ar) / sizeof(datatype);

        Inithash_table();

        for (int i = 0; i < n; i++)
                Insert_new_element(ar + i);
        
        Showhash_table();

        exit(EXIT_SUCCESS);
}

void Inithash_table()
{
        for (int i = 0; i < P; i++)
        {
                for (int j = 0; j < BUCKET_NODE_SIZE; j++)
                        hash_table[i].data[j] = NULL_DATA;
                hash_table[i].next = NULL;
        }
}

static int Hash(datatype *key)
{
        return *key % P;
}

void Insert_new_element(datatype *key)
{
        int index = Hash(key);
        for (int i = 0; i < BUCKET_NODE_SIZE; ++i)
        {
                if (hash_table[index].data[i] == NULL_DATA)
                {
                        hash_table[index].data[i] = *key;
                        return;
                }
        }
        struct bucket_node *ptr = &hash_table[index];
        while (ptr->next != NULL)
        {
                ptr = ptr->next;
                for (int i = 0; i < BUCKET_NODE_SIZE; i++)
                {
                        if (ptr->data[i] == NULL_DATA)
                                ptr->data[i] = *key;
                        return;
                }
        }
        struct bucket_node *current = malloc(sizeof(struct bucket_node));
        for (int i = 0; i < BUCKET_NODE_SIZE; i++)
                current->data[i] = NULL_DATA;
        current->next = NULL;
        current->data[0] = *key;
        ptr->next = current;
}

void Showhash_table()
{
        for (int i = 0; i < P; i++)
        {
                printf("%d : ", i);
                struct bucket_node *ptr = &hash_table[i];
                while (ptr != NULL)
                {
                        printf("[");
                        for (int i = 0; i < BUCKET_NODE_SIZE; i++)
                        {
                                if (ptr->data[i] == NULL_DATA)
                                        printf(".");
                                else
                                        printf("%d-->", ptr->data[i]);
                        }
                        printf("]");
                        ptr = ptr->next;
                }
                printf("Nul.\n");
        }
}